High compression gains for video sequences can be achieved by removing temporal redundancies between images (frames). For example, to encode an image, a temporal prediction of the image to be encoded is generated based on previously encoded images. The temporal prediction is compared with the actual image to determine the prediction error, and the prediction error is encoded. The prediction can be made using block-based motion estimation and compensation methods, which are widely used (e.g., MPEG standards).
Motion compensation and estimation methods are used to find a reference block in one or more reference images to predict the location of a corresponding target block in the target image, so that only the prediction residual of the target block needs to be coded, which is typically the prediction error and the motion vector. These methods perform block matching to identify a reference block of pixels in the reference image that is most similar to a corresponding target block in the target image.
The pixel distance between the reference block and corresponding target block is the motion vector for the target block. For example, let mxi,j, myi,j be the motion vector of a block Bi,j at the x-axis (horizontal) and y-axis (vertical), respectively. The values of the motion vector are used in video compression, along with the reference block, to generate a prediction value for the target block.
FIG. 1 is a diagrammatic view of an illustrative motion vector. Target image 120 is to be encoded using information from reference image 110. Reference block 115 is identified as the block in reference image 110 that most closely matches a target block 125 in target image 120. After the reference block is identified, motion vector 130 (shown as an arrow for illustrative purposes only) is generated to identify the position of target block 125 relative to the position of reference block 115. Motion vector 130 has two elements that represent the relationship between reference block 115 and target block 125: a horizontal displacement and a vertical displacement. For example, reference block 115, which is an illustrative 3×3 group of pixels, is at location (i′, j′), and target block 125 is at location (i,j). The distance between the two blocks is the motion vector (i′-i,j′-j).
To identify the reference block in the reference image, candidate blocks in the reference image are compared to the target block. Each candidate block has the same size as the target block and is located within a specified search range in the reference image. The candidate block that most closely matches the target block is identified as the reference block. Searching for the reference block is a significant part of motion estimation and usually requires a large amount of arithmetic computation.
The complexity of performing motion estimation for one target block is proportional to the number of possible reference blocks within the search range, which is proportional to the square of the motion search range, or distance d, e.g., Complexity=α×d2, where α is a constant. The motion search range defines the area in the reference image that is used to find the reference block. In other words, the search range specifies the number of blocks in the reference image to be examined during motion estimation.
The motion search range should be related to the speed of the movement of the object in the image. For example, for fast moving objects, a large search range is appropriate to find a good counter-block to predict the target block. However, predicting which part of the image (or frame) has a small amount of motion and which part has a large amount of motion is difficult if done before performing the motion estimation method. Therefore, typical video compression methods use a fixed motion search range for all the blocks in the same target image.
The drawback of a fixed motion search range is that if it is large enough to capture the fastest moving object in the image, it unnecessarily increases the search computation for the regions with small movement. Conversely, if the search range is too small, the motion estimation method may not be able to find the reference block which has a large amount of movement, because the reference block may be outside of the search range.